# -*- coding: utf-8 -*- 
# @File : test.py
# @Time : 2019/10/17 10:09 
# @Author : yaozi
# @Contact : xt1512326654@sina.cn
import time

from Stack import Stack
from graphics import Point
from myarray2d import Array2D
from myqueue import Queue


def arrayTestBFS():
    a = Array2D(5, 5)
    a[0, 0] = 0
    a[0, 1] = 0
    a[0, 2] = 1
    a[0, 3] = 0
    a[0, 4] = 0

    a[1, 0] = 1
    a[1, 1] = 0
    a[1, 2] = 0
    a[1, 3] = 0
    a[1, 4] = 0

    a[2, 0] = 0
    a[2, 1] = 0
    a[2, 2] = 1
    a[2, 3] = 0
    a[2, 4] = 0

    a[3, 0] = 0
    a[3, 1] = 0
    a[3, 2] = 0
    a[3, 3] = 1
    a[3, 4] = 1

    a[4, 0] = 0
    a[4, 1] = 1
    a[4, 2] = 0
    a[4, 3] = 0
    a[4, 4] = 0

    start = Point(0, 0)
    flag = Point(4, 4)
    for rows in range(a.numCols()):
        for cols in range(a.numRows()):
            print(a[rows, cols], end=" ")
            if (cols + 1) % a.numCols() == 0:
                print("\n", end="")
    print("\n", end="")
    pathSearch(a, start, flag)


def pathSearch(array, start_point, target_point):
    """
    路径搜索
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :return:
    """
    came_from = {}
    t1 = time.perf_counter()
    found = breadthFirstSearch(array, start_point, target_point, came_from)
    # found = breadthFirstSearchQueue(array, start_point, target_point, came_from)
    # found = depthFirstSearch(array, start_point, target_point, came_from)
    t2 = time.perf_counter()
    print(t2 - t1)
    if found is not None:
        pathFinishing = Stack()
        pathFinishing.push(found)
        found = came_from.get(found)
        while found is not None:
            pathFinishing.push(found)
            found = came_from.get(found)
        while not pathFinishing.is_empty():
            print(pathFinishing.pop(), end='->\n')


def breadthFirstSearch(array, start_point, target_point, came_from):
    """
    宽度优先搜索/广度优先搜索，核心代码
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :param came_from:
    :return:
    """
    # 未访问位置存储
    noVisited = [start_point]
    # 已访问存储节点
    hasVisited = []
    # 用来存放路径链
    came_from[start_point] = None
    while len(noVisited) != 0:
        start_point = noVisited.pop(0)
        if int(start_point.x) == int(target_point.x) and int(start_point.y) == int(target_point.y):
            return start_point
        else:
            hasVisited.append(start_point)
            # 获取邻近节点
            for point in getAdjacentPointWithNoVisited(array, start_point, hasVisited):
                noVisited.append(point)
                came_from[point] = start_point
    return None


def breadthFirstSearchQueue(array, start_point, target_point, came_from):
    """
    宽度优先搜索/广度优先搜索，核心代码
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :param came_from:
    :return:
    """
    # 未访问位置存储
    noVisited = Queue()
    noVisited.enqueue(start_point)
    # 已访问存储节点
    hasVisited = {}
    # 用来存放路径链
    came_from[start_point] = None
    while not noVisited.is_empty():
        start_point = noVisited.dequeue()
        if int(start_point.x) == int(target_point.x) and int(start_point.y) == int(target_point.y):
            return start_point
        else:
            hasVisited[start_point] = True
            # 获取邻近节点
            for point in getAdjacentPointWithNoVisited(array, start_point, hasVisited):
                noVisited.enqueue(point)
                came_from[point] = start_point
    return None


def depthFirstSearch(array, start_point, target_point, came_from):
    """
    深度优先搜索
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :param came_from:
    :return:
    """
    noVisited = Stack()
    noVisited.push(start_point)
    came_from[start_point] = None
    # 字典
    hasVisited = {}
    while not noVisited.is_empty():
        start_point = noVisited.pop()
        if hasVisited.get(start_point) is None:
            if int(start_point.x) == int(target_point.x) and int(start_point.y) == int(target_point.y):
                return start_point
            else:
                hasVisited[start_point] = True
                for point in getAdjacentPointWithNoVisited(array, start_point, hasVisited):
                    noVisited.push(point)
                    came_from[point] = start_point
    return None


def depthFirstSearchQueue(array, start_point, target_point, came_from):
    """
    深度优先搜索
    :param array: 参数是二维数组，用来记录整个迷宫位置
    :param start_point: 起点，类型为Point
    :param target_point: 目标点，类型为Point
    :param came_from:
    :return:
    """
    noVisited = Stack()
    noVisited.push(start_point)
    came_from[start_point] = None
    # 字典
    hasVisited = {}
    while not noVisited.is_empty():
        start_point = noVisited.pop()
        if hasVisited.get(start_point) is None:
            if int(start_point.x) == int(target_point.x) and int(start_point.y) == int(target_point.y):
                return start_point
            else:
                hasVisited[start_point] = True
                for point in getAdjacentPointWithNoVisited(array, start_point, hasVisited):
                    noVisited.push(point)
                    came_from[point] = start_point
    return None


def getAdjacentPointWithNoVisited(array, point, visited):
    """
    检查相邻坐标的可执行坐标（未访问坐标）
    :param array: 二维数组
    :param point: 待检查点
    :param visited: 已经访问节点记录
    :return: 返回与此point相邻未访问节点的节点，如果该节点不存在未访问的节点返回None
    """
    filterValue = 1
    cols = array.numCols()
    rows = array.numRows()
    pointX = int(point.x)
    pointY = int(point.y)
    # 检查当前节点的合法性
    if array[pointX, pointY] != 1:
        near = []
        if 0 <= pointX <= cols and 0 <= pointY <= rows:
            # TOP 检查该节点的上节点是否可行
            if 0 <= pointY - 1 and array[pointX, pointX - 1] != filterValue:
                i = 0
                for points in visited:
                    # 如果该节点上节点存在定flag为1，否则代表visited中不存在该节点的上节点
                    if int(points.x) == pointX and int(points.y) == pointY - 1:
                        i = 1
                if i == 0:
                    near.append(Point(int(points.x), pointY - 1))
            # RIGHT 检查该节点右节点是否可行
            if pointX + 1 < cols and array[pointX + 1, pointX] != filterValue:
                i = 0
                for points in visited:
                    if int(points.x) == pointX + 1 and int(points.y) == pointX:
                        i = 1
                if i == 0:
                    near.append(Point(pointX + 1, pointX))
            # BOTTOM 检查该节点下节点是否可行
            if pointY + 1 < rows and array[pointX, pointX + 1] != filterValue:
                i = 0
                for points in visited:
                    if int(points.x) == pointX and int(points.y) == pointY + 1:
                        i = 1
                if i == 0:
                    near.append(Point(int(points.x), pointY + 1))
            # LEFT 检查该节点左节点是否可行
            if 0 <= pointX - 1 and array[pointX - 1, pointX] != filterValue:
                i = 0
                for points in visited:
                    if int(points.x) == pointX - 1 and int(points.y) == pointX:
                        i = 1
                if i == 0:
                    near.append(Point(pointX - 1, pointX))
        return near
    return None


if __name__ == '__main__':
    arrayTestBFS()
